package pure.engine.world.path 
{
    import flash.geom.Point;

internal class Path
{	
	public function Path(numCol:int, numRow:int) {
		_numCol = numCol;
		_numRow = numRow;
		_nodes = new Array();
		for(var i:int = 0; i < _numCol; i++){
			_nodes[i] = new Array();
			for(var j:int = 0; j < _numRow; j++){
				_nodes[i][j] = new Node(i, j);
			}
		}
	}
	
	
	/* model */
	private var _open:Array; // 待考察列表需要多次重复排查
	private var _closed:Array; // 已考察列表要进行迭代排除
	private var	_pathData:Array;
	private var _nodes:Array;
	private var	_numCol:int;
	private var _numRow:int;
	/* other */
	private var _endNode:Node;
	private var _startNode:Node;
	private var	_straightCost:Number = 1.0;
	private var	_diagCost:Number = Math.SQRT2;
//	private var _heuristic:Function = diagonal;
//	private var _heuristic:Function = manhattan;
	private var _heuristic:Function = euclidian;

	/**
	 * 寻路
	 * @param start		起点
	 * @param end		终点
	 */
	internal function findPath(start:Point=null, end:Point=null):Boolean {
		_open = [];
		_closed = [];
		if (start) _startNode = _getNode(start.x, start.y);
		if (end) _endNode = _getNode(end.x, end.y);
		_startNode.g = 0;
		_startNode.h = _heuristic(_startNode);
		_startNode.f = _startNode.g + _startNode.h;
		return search();
	}

	internal function setWalkable(x:int, y:int, b:Boolean):void {
		_nodes[x][y].walkable = b;
	}

	internal function getWalkable(x:int, y:int):Boolean {
		return (_nodes[x][y] as Node).walkable;
	}
	
	
	

	/* ----------------------------------------------------------------------------------------------------------------
	 * ★★★★★★★★★★★★★★★★★★★★★  get × set  ★★★★★★★★★★★★★★★★★★★★★
	 * ----------------------------------------------------------------------------------------------------------------
	 */
		
	 
	 
	 
	/* 路径 */
	internal function get pathData():Array { return _pathData; }
	
	// 总列数
	internal function get numCols():int { return _numCol; }

	// 总行数
	internal function get numRows():int { return _numRow; }

	// 起点
	internal function get startNode():Node { return _startNode; }
	
	// 终点
	internal function get endNode():Node { return _endNode; }
	
	public function get visited():Array { return _closed.concat(_open); }
	public function get closed():Array { return _closed; }
	public function get open():Array { return _open; }
	


	
	/* ----------------------------------------------------------------------------------------------------------------
	 * ★★★★★★★★★★★★★★★★★★★★★  private  ★★★★★★★★★★★★★★★★★★★★★
	 * ----------------------------------------------------------------------------------------------------------------
	 */
	
	
	
	
	private function search():Boolean {
		var node:Node = _startNode;
		while(node != _endNode) {
			var startX:int = Math.max(0, node.x - 1);
			var endX:int = Math.min(_numCol - 1, node.x + 1);
			var startY:int = Math.max(0, node.y - 1);
			var endY:int = Math.min(_numRow - 1, node.y + 1);
			
			for(var i:int = startX; i <= endX; i++){
				for(var j:int = startY; j <= endY; j++){
					var test:Node = _getNode(i, j);
					if(test == node || !test.walkable ){
						continue;
					}
					if (i != node.x && j != node.y){
						var test2:Node = _getNode(node.x, j);
						if (!test2.walkable){
							continue;
						}
						test2 = _getNode(i, node.y);
						if (!test2.walkable){
							continue;
						}
					}
					if((node.x == test.x) || (node.y == test.y)){
						var cost:Number = _straightCost;
					}
					else{
						cost = _diagCost;
					}
					var g:Number = node.g + cost * test.costMultiplier;
					var h:Number = _heuristic(test);
					var f:Number = g + h;
					if(isOpen(test) || isClosed(test)) {
						if(test.f > f) {
							test.f = f;
							test.g = g;
							test.h = h;
							test.parent = node;
						}
					}
					else {
						test.f = f;
						test.g = g;
						test.h = h;
						test.parent = node;
						_open.push(test);
					}
				}
			}
			for(var o:int = 0; o < _open.length; o++)
			{
			}
			_closed.push(node);
			if(_open.length == 0) {
				trace("no path found");
				return false
			}
			_open.sortOn("f", Array.NUMERIC);
			node = _open.shift() as Node;
		}
		buildPath();
		return true;
	}
	
	private function buildPath():void {
		_pathData = [];
		var node:Node = _endNode;
		_pathData.push(node);
		while(node != _startNode){
			node = node.parent;
			_pathData.unshift(node);
		}
	}
	
	private function _getNode(x:int, y:int):Node {
		return _nodes[x][y] as Node;
	}
	
	/**
	  * 节点是否在open列表中
	  */
	private function isOpen(node:Node):Boolean {
		if (_open.indexOf(node) != -1) return true;
		return false;
	}
	
	/**
	  * 节点是否在close列表中
	  */
	private function isClosed(node:Node):Boolean {
		if (_closed.indexOf(node) != -1) return true;
		return false;
	}
	
	/* 曼哈顿 */
	private function manhattan(node:Node):Number
	{
		return Math.abs(node.x - _endNode.x) * _straightCost + Math.abs(node.y + _endNode.y) * _straightCost;
	}
	
	/* 直线 */
	private function euclidian(node:Node):Number
	{
		var dx:Number = node.x - _endNode.x;
		var dy:Number = node.y - _endNode.y;
		return Math.sqrt(dx * dx + dy * dy) * _straightCost;
	}
	
	/* 对角线 */
	private function diagonal(node:Node):Number
	{
		var dx:Number = Math.abs(node.x - _endNode.x);
		var dy:Number = Math.abs(node.y - _endNode.y);
		var diag:Number = Math.min(dx, dy);
		var straight:Number = dx + dy;
		return _diagCost * diag + _straightCost * (straight - 2 * diag);
	}

}
}

